A typical data communications network includes many hosts interconnected by various data communication devices. The data communication devices can be routers, bridges, switches, access servers, gateways, hubs, proxy servers, repeaters and so forth which exchange data over an interconnection of data links. The data links may be physical cables or may be provided using wireless communication mechanisms. The network allows data to propagate between sending and receiving hosts. The sending and receiving hosts are often general purpose computer systems such as personal computers, workstations, minicomputers, mainframes and the like, or the hosts may be dedicated devices such as web-site kiosks, facsimile servers, video servers and so forth. Each host couples to one or more of the data communications devices that form the network.
Various physical data communications connection mechanisms allow hosts to interconnect with the network. Physical data communications connection mechanisms such as modems, transceivers, network interface cards, fiber optic cards, ports or other hardware devices allow data to be transferred at various maximum and minimum data transfer rates to and from the hosts. For example, certain hosts may have high-speed network interfaces which provide physical connections to the network at high data rates such as fractional T1, T1, E1 or higher, while other hosts may use an inexpensive modem that provides a maximum data transfer rate of 56.6 kilobits per second (Kbps) to and from the network.
Depending upon the specific use or application running on a host, different levels of service (i.e., data transfer rates) may be required for data transmitted to and from the host. For example, hosts that-connect or subscribe to networks using high speed connection mechanisms such T1 cards generally expect to be provided with, and often pay a premium for the ability to send and receive data at T1 data rates. Other hosts may not require such high data transfer rates and therefore only subscribe to the network and pay for the capability to transfer data at lower data transfer rates.
Since connections or data traffic flows from multiple hosts with potentially different data rates are frequently switched, routed or transferred through the same data communication devices in a network such as the Internet, the data communications devices must provide a way to distinguish the different data flows or connections requiring different levels of service (i.e., different data rates). Once distinguished, the data communications devices must be able to service each connection or flow at its prescribed level of service. Thus, data transmitted over a T1 link must generally be transported,through the network at T1 speeds, while data from a slower link should at least be transferred through the network at a minimum subscription rate. Management of the various delay requirements associated with data having differing levels of service is a well known problem associated with data communications devices in modern networks.
The problem of delay management also stems from the various types of data that can be transmitted through a network between sending and receiving hosts. For example, modem data, facsimile data, video data, voice data or other data types may all be transmitted using packets, cells, frames or another mechanism over a commonly shared network medium. Each of these data types may have certain Quality of Service (QoS) requirements with respect to how quickly that data must be transferred through the network.
Video and voice data, for instance, generally must be transferred in real-time over a network so that a receiving host can correctly reconstruct a video or voice signal from the data. If real-time transmission is not provided and the data is delayed too long in the network, the viewer or listener at the receiving host may experience drops outs or degraded service. Conversely, many types of modem data transmissions such as e-mail communications, for example, typically have no specific bandwidth, QoS, or delay requirements to be met as the data is propagated through the network. In between these two extremes, data such as facsimile data may require adherence to certain minimum protocol delay or quality of service requirements which do not rise to the demands of real-time transmission but which also cannot allow for significant delays in transmission.
Other examples of delay management can arise when certain data communication protocols require data to be delivered according to certain delay attributes. An example of this is the use of specialized protocols for remote sensing and process control applications, where data must be exchanged in a timely manner to correctly operate equipment in response to a stimulus. Whether delay requirements are due to varying data transmission rates, different data types, specialized protocols requiring minimum QoS levels or other concerns, the data communications devices in a network are generally responsible for managing the delay of data as it propagates through the network.
Various prior art schemes have been developed to allow a data communications device to handle the transfer of data at differing levels of service. Most involve providing separate data queues for the different types of data or different levels of service and use a weighted round-robin or other type of queue servicing algorithm or de-queuing mechanism to remove data for transmission from the various queues at different rates. For example, a high priority queue may be serviced twice as often as a low priority queue, thus allowing twice as much high priority data to propagate through the device. In this manner, prior art systems attempt to control delay and priority of data passing through the network using separate delay control mechanisms for each type of data.
Embodiments of the present invention relate to delay management, scheduling and controlling the delay of data passing through a data communications device in a data communications network. More specifically, the invention relates to a unique and flexible queuing, storage and delay scheduling mechanism that allows a delay scheduling process to delay data having various attributes.
According to one aspect of the invention, a delay manager apparatus and method are provided to schedule delays of data in a data communications device. The apparatus includes an input for receiving unscheduled data and a delay controller which includes a predetermined number of storage locations. The apparatus and method involve managing the delay of data in the data communications device by configuring a predetermined number of the storage locations. to store data passing through the data communications device, with each storage location having an associated delay.
A data scheduler is provided and is coupled to the input to receive the unscheduled data. The data scheduler determines a delay associated with the unscheduled data and deposits the unscheduled data into one of the predetermined number of storage locations in the delay controller. The selected storage location has a predetermined associated delay that generally corresponds to the delay associated with the unscheduled data. The delay controller includes a delay control processor which adjusts the associated delay over time of data deposited in each of the predetermined number of storage locations. A transmission buffer is coupled to the delay controller, and transmits data deposited into a storage location that has an associated delay equal to a predetermined delay transmit value. In this manner, the invention imposes delays on data passing through a data communications device.
Preferably, the delay manager also includes a policy controller coupled to the data scheduler and the delay controller. The policy controller receives a network policy which defines delay categories for data passing through the data communications device. The policy controller analyzes the network policy and provides control commands to the data scheduler and the delay controller which indicate to the data scheduler the delay categories that can be associated with the unscheduled data and also indicate to the delay controller the predetermined number of storage locations required to store data in each delay category. The control commands also indicate a rate at which to adjust the associated delay over time of data deposited in each of the predetermined number, of storage locations. The control commands establish a delay management configuration based on the network policy which allows data of different types to be scheduled together in a single mechanism. If the network policy changes, the invention can detect this and can adjust the delay management configuration to respond to the changes.
According to another aspect of the invention, the delay controller includes a series of interconnected registers and a first register in the series has the lowest associated delay and the last register in the series has the highest associated delay. The registers in the series located between the first and last register have incrementally increasing associated delay categories or delay time values. During configuration, the predetermined number of storage locations in the data controller are selected from the series of interconnected registers such that each selected register in the series represents a storage location having an associated delay equal to a delay category determined from the network policy. This allows the invention to be flexible in the event of network policy changes.
According to another aspect of the invention, the delay controller apparatus includes a speed controller or a speed and direction controller which adjusts the delay associated with data deposited into storage locations. This is done by decrementally shifting the data from storage locations having higher associated delay categories to storage locations having lower associated delay categories. When the data is shifted into the storage location having the lowest associated delay category, the speed or speed and direction controller transfers the data to the transmission buffer for transmission.
An embodiment of the invention also includes a method for managing delay of data in a data communications device. The method involves establishing multiple delay categories based on a network policy. The method further involves obtaining data and assigning a delay to the data based on which of the established delay categories an attribute of that data identifies. The delay assigned to data is then adjusted over time and the data is transmitted when the delay assigned to the data reaches a predetermined delay transmit value.
A more detailed method embodiment provides a method for managing delay of data in a data communications device by configuring a predetermined number of storage locations, preferably located within a delay controller, to store data passing through the data communications device, where each storage location has an associated delay. Data is then accepted, preferably by a data scheduler, and a delay associated with the data is determined by the data scheduler. The data scheduler then deposits the data into a selected storage location selected from the predetermined number of storage locations. The selected storage location has an associated delay generally corresponding to the delay determined to be associated with the data. The delay controller then adjusts the associated delay over time for data deposited in each of the predetermined number of storage locations. The data deposited in a storage location that has an associated delay generally equal to a predetermined delay transmit value is then transmitted, preferably to a transmit buffer.
According to another aspect of the invention, to establish the predetermined number of storage locations, a policy controller determines a required number of delay categories associated with data that can be transmitted through the data communications device. The number of delay categories is preferably based upon a network policy provided by a network policy server to the policy controller. Based upon the required number of delay categories, the policy controller computes the predetermined number of storage locations to establish. Preferably, the policy controller selects or allocates the predetermined number of storage locations from a series of interconnected registers. Next, a rate at which to adjust the associated delay over time for data deposited in each of the predetermined number of storage locations can be computed and communicated to the delay controller from the policy controller. The rate governs a direction and speed at which to traverse the predetermined number of storage locations in the delay controller to adjust the associated delay over time for data deposited in each of the predetermined number of storage locations. In this embodiment, the total number of the predetermined number of storage locations determines an overall maximum delay for data.
According to yet another aspect of the invention, to adjust the associated delay over time for data deposited in each of the predetermined number of storage locations, a speed controller in the delay controller transfers the data in each respective storage location to a storage location having a lower associated delay. As such, successive adjusting steps move data from storage locations having high associated delays to storage locations having lower associated delays. Delays may be increased in an alternative embodiment by shifting data in the reverse direction. Data is transmitted when the data is deposited in a storage location having a lowest delay transmit value, such as zero.
Depending upon the positioning of the invention in a data communications device, data can be accepted by a delay manager from a network port of the data communications device and this data can be transmitted to a data processor within the data communications device after the delay manager manages delays of the data according to the invention. In this instance, the delay associated with data is controlled as the data arrives at the data communications device. Alternatively, data can be accepted by the delay manager from a data processor within the data communications device and can be transmitted to a network port of the data communications device after being delayed, such that the delay associated with data is controlled as the data awaits transmission from the data communications device.
Embodiments of the invention can determine a delay associated with the data based upon can attribute associated with the data, such as a type of service associated with the data, a source or destination or the data, a protocol or application used to create or transfer the data, a data type associated with the data or another aspect of the data. The attribute may be contained within the data itself, or may be obtained from another indicator such as the source processor, interface, device, port or link that provided the data. Using these mechanisms, the invention can schedule data having different attributes.
The invention may be provided on a per port, per processor, per interface or per link basis, such that a single data communications device may have many delay managers configured according to the invention. In such embodiments, each delay manager manages delay for individual streams of data: flowing through respective ports, interfaces, links, and so forth. Alternatively, a data communications device may have a single delay manager configured according to the invention to manage and schedule delays for all data passing through the device.
According to another aspect of the invention, updates to the network policy can be obtained by the policy controller and the storage locations in the delay controller can be reconfigured during operation of the data communications device to allow controlling a delay for data transmitted through the data communications device according to the updates in the network policy. In this manner, a data communications device using the invention offloads from the network policy server the burden of distributing any updates to the network policy. This allows each device to obtain the updates from a network policy server as needed, instead of requiring the network policy server to actively distribute new policies all at once. This distributes the load on the network policy server.
Other embodiments of the invention include a computer program product including a computer-readable medium, such as a disk, including computer program logic encoded thereon. The computer program logic, typically in the form of object code, can execute on a processor. The code causes the processor, in conjunction with other mechanisms (i.e. memory, bus structures, interfaces, etc.) in a data communications device to control the delay of data according to the methods set forth herein. Thai is, the invention may be implemented as a software program that can be stored on a computer readable medium and can provide the delay functions and operation and storage locations with such mechanisms as source code that, when compiled and executed, can instantiate data structures including linked lists, queues, and other programming techniques that use memory and the processor and other mechanisms to store and manipulate data as explained herein. Generally, this embodiment of the invention includes software to implement the methods of the invention described above.
A data communications device equipped with the methods and apparatus of the invention is able to dynamically alter data traffic flow delay characteristics and delay management configurations as needed. In this manner, resources such as storage locations used by the invention within the device can be intelligently reserved only as required by the network policy.